/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/interval-sum-ii
   @Language: C++
   @Datetime: 19-04-01 14:25
   */

class Solution {
	struct SegmentTreeNode{
		int start, end;
		long long val;
		SegmentTreeNode *left, *right;
		SegmentTreeNode(int start, int end, long long val){
			this->start=start;
			this->end=end;
			this->val=val;
			this->left=this->right=NULL;
		}
	};
	SegmentTreeNode *m_root;

	SegmentTreeNode *build(vector<int> &A, int start, int end){
		if(A.size()<1 || start>end) return NULL;
		SegmentTreeNode *root=new SegmentTreeNode(start, end, A[start]);
		if(start==end) return root;
		root->left=build(A,start,(start+end)/2);
		root->right=build(A,(start+end)/2+1,end);
		root->val=root->left->val+root->right->val;
		return root;
	}
	long long query(SegmentTreeNode *root, int start, int end) {
		// write your code here
		if(root==NULL || start>root->end || end<root->start) return 0;
		if(start==root->start && end==root->end) return root->val;
		int mid=(root->start+root->end)/2;
		if(start>mid) return query(root->right,start,end);
		if(end<=mid) return query(root->left,start,end);
		return query(root->left,start,mid)+query(root->right,mid+1,end);
	}
	void modify(SegmentTreeNode *root, int index, int value) {
		// write your code here
		if(root==NULL || index>root->end || index<root->start) return;
		if(root->start==index && root->end==index){
			root->val=value;
			return;
		}
		modify(root->left,index,value);
		modify(root->right,index,value);
		root->val=root->left->val+root->right->val;
	}
	void destroy(SegmentTreeNode *root){
		if(root==NULL) return;
		destroy(root->left);
		destroy(root->right);
		delete root;
	}
public:
	/* you may need to use some attributes here */

	/*
	 * @param A: An integer array
	 */
	Solution(vector<int> &A) {
		// do intialization if necessary
		m_root=build(A,0,A.size()-1);
	}
	~Solution(){
		destroy(m_root);
	}

	/*
	 * @param start: An integer
	 * @param end: An integer
	 * @return: The sum from start to end
	 */
	long long query(int start, int end) {
		// write your code here
		return query(m_root,start,end);
	}

	/*
	 * @param index: An integer
	 * @param value: An integer
	 * @return: nothing
	 */
	void modify(int index, int value) {
		// write your code here
		modify(m_root,index,value);
	}
};

